1. Technical Field
The present invention relates to code optimization. In particular, the present invention relates to code optimization through auto parallelization of zero-trip loops.
2. Description of Related Art
A basic induction variable is a variable that is only determined inside a loop, whose value is incremented or decremented by a constant value. The most common place to find the use of induction variables is in array subscripts. Induction variable substitution finds variables which form arithmetic and geometric progressions and which can be expressed as functions of the indices of enclosing loops, then replaces these variables with the expressions involving loop indices. Induction variable substitution plays a very important role in resolving data dependencies and enabling loop parallelization. Loop parallelization by a compiler attempts to parallelize loops to speed up execution. Parallelizing is to generate instructions for a parallel processing computer. For example, the code segment in the left side of the example depicted in FIG. 1, which demonstrates an induction variable substitution, cannot be parallelized due to the loop carried dependency on induction variable (IV). Induction variable substitution is used to solve this problem. After induction variable substitution, the dependency would be eliminated and the loop can be parallelized as shown in the right side of the example depicted in FIG. 1.
For the nested induction variables, the substitution can be processed recursively starting from the innermost loop. A zero-trip loop is a loop that, depending on the values of the starting value and the limit, it is possible to ‘skip’ the loop entirely. In case of zero-trip loop, the number of iterations calculated from the parameters of the loop is less than 1 and the simple substitution would cause a problem. Take the exemplary Fortran code segment in FIG. 2, which is a zero-trip loop code. Applying substitution to the nested induction variable IV in the code of FIG. 1, the variable IV would be expressed as: IV=I+J*N if the value of N is positive. However, if N is non-positive, the result of the substitution would be incorrect.